package com.mdnote.practice.linked_list;

import org.junit.Test;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/20 15:30
 * @Email rhythm_2019@163.com
 * @Description 147. 对链表进行插入排序
 */
public class LeetCode147 {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode cur = head;
        ListNode dumpNode = new ListNode(-1);
        dumpNode.next = head;
        while (cur.next != null) {

            if (cur.val <= cur.next.val) {
                cur = cur.next;
            } else {
                ListNode tmp = cur.next;
                cur.next = cur.next.next;

                // 找到合适位置
                ListNode pre = dumpNode;
                while (pre.next != null  && pre.next.val <= tmp.val) {
                    pre = pre.next;
                }
                // insert into between pre and pre.next
                tmp.next = pre.next;
                pre.next = tmp;
            }

        }
        return dumpNode.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    @Test
    public void test_01() {
        LeetCode147 leetCode328 = new LeetCode147();
        ListNode head = new ListNode(4);
        head.next = new LeetCode147.ListNode(2);
        head.next.next = new LeetCode147.ListNode(1);
        head.next.next.next = new LeetCode147.ListNode(5);
        head.next.next.next.next = new LeetCode147.ListNode(3);
        head.next.next.next.next.next = new LeetCode147.ListNode(7);
        ListNode listNode = leetCode328.insertionSortList(head);

        ListNode tmpNode = listNode;
        while (tmpNode != null) {
            System.out.println(tmpNode.val);
            tmpNode = tmpNode.next;
        }


    }
}
